use std::fmt::Write;

pub fn min_edge_prime_num(threshold: u32) -> String {
    let mut side_length = 1;
    let mut number_of_primes = 0;
    let mut number_of_diagonals = 1;
    let mut n = 1u64;

    loop {
        side_length += 2;
        let step = side_length - 1;
        for _ in 0..4 {
            n += step as u64;
            if is_prime(n) {
                number_of_primes += 1;
            }
        }
        number_of_diagonals += 4;

        let ratio = (number_of_primes as f64) / (number_of_diagonals as f64) * 100.0;
        if ratio < threshold as f64 {
            let mut result = String::new();
            write!(result, "{},{}", side_length, number_of_primes).unwrap();
            return result;
        }
        if ratio < 7.0 {
            break;
        }
    }

    String::from("Proportion will not go below 7%")
}

// Miller-Rabin 素性测试
fn is_prime(n: u64) -> bool {
    if n < 2 {
        return false;
    }
    if n == 2 || n == 3 {
        return true;
    }
    if n % 2 == 0 {
        return false;
    }

    // 将 n-1 分解为 d * 2^s
    let mut d = n - 1;
    let s = d.trailing_zeros();
    d >>= s;

    let bases: &[u64] = &[2, 3, 5, 7, 11, 13, 17];

    for &a in bases {
        if a >= n {
            continue;
        }
        let mut x = mod_pow(a, d, n);
        if x == 1 || x == n - 1 {
            continue;
        }
        let mut is_composite = true;
        for _ in 0..s - 1 {
            x = mod_mul(x, x, n);
            if x == n - 1 {
                is_composite = false;
                break;
            }
        }
        if is_composite {
            return false;
        }
    }
    true
}

fn mod_pow(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
    let mut result = 1u64;
    base %= modulus;
    while exp > 0 {
        if exp % 2 == 1 {
            result = mod_mul(result, base, modulus);
        }
        base = mod_mul(base, base, modulus);
        exp /= 2;
    }
    result
}

fn mod_mul(a: u64, b: u64, modulus: u64) -> u64 {
    ((a as u128 * b as u128) % modulus as u128) as u64
}